package cliqueproblem;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.List;
import org.jgrapht.UndirectedGraph;
import org.jgrapht.alg.NeighborIndex;
import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.graph.SimpleGraph;

/**
 *
 * @author Krasnoperov Alexey
 */
public class JohnstonsAlgorithm {

	UndirectedGraph<Vertex, DefaultEdge> mainGraph;
	UndirectedGraph<Vertex, DefaultEdge> maxClique =
		new SimpleGraph<Vertex, DefaultEdge>(DefaultEdge.class);
	int maxCliqueSize = 0;
	int cliqueCount = 0;

	public JohnstonsAlgorithm(UndirectedGraph<Vertex, DefaultEdge> g) {
		mainGraph = g;
	}

	public void findCliques() {
		extend(
			new ArrayList<Vertex>(),
			new ArrayList<Vertex>(mainGraph.vertexSet()),
			new ArrayList<Vertex>(mainGraph.vertexSet()));
		System.out.println("Total cliques found: " + cliqueCount);
		System.out.println("Maximal clique size: " + maxCliqueSize);
	}

	// Main iterator for finding maximal clique
	private void extend(List<Vertex> combination, List<Vertex> intersection, List<Vertex> possible) {
		if (intersection.isEmpty()) {
			if (combination.size() > maxCliqueSize) {
				maxCliqueSize = combination.size();
				maxClique.removeAllVertices(mainGraph.vertexSet());
				for (Vertex curVertex : combination) {
					maxClique.addVertex(curVertex);
				}
			}
			cliqueCount++;
		} else {
			Queue<Vertex> S = new LinkedList<Vertex>(calculate(possible, intersection));
			while (!S.isEmpty()) {
				Vertex I = S.poll();
				possible.remove(I);

				List<Vertex> newcombination = new ArrayList<Vertex>(combination);
				List<Vertex> newintersection = new ArrayList<Vertex>(intersection);
				List<Vertex> newpossible = new ArrayList<Vertex>(possible);
				newcombination.add(I);
				newintersection.retainAll(neighbours(I, intersection));
				newpossible.retainAll(neighbours(I, possible));

				extend(newcombination, newintersection, newpossible);
			}
		}
	}

	// The generalized Bron-Kerbosh method
	private List<Vertex> calculate(List<Vertex> possible, List<Vertex> intersection) {
		List<Vertex> S = new ArrayList<Vertex>();
		// Threshold may be any int >= 0
		// threshold = 25 is equal to threshold = infinity, so
		// here we implements simplified BK method, which is best
		// for our graphs
		int threshold = 25;
		int sizeOfS = Integer.MAX_VALUE;
		Queue<Vertex> T = new LinkedList<Vertex>(intersection);

		while (!T.isEmpty() && sizeOfS > threshold) {
			Vertex J = T.poll();
			List<Vertex> newS = new ArrayList<Vertex>(possible);
			newS.removeAll(neighbours(J, newS));
			int newSize = newS.size();
			if (newSize < sizeOfS) {
				S = newS;
				sizeOfS = newSize;
			}
		}

		return S;
	}

	// Neighbors of vertex in set
	private List<Vertex> neighbours(Vertex v, List<Vertex> set) {
		NeighborIndex<Vertex, DefaultEdge> n =
			new NeighborIndex<Vertex, DefaultEdge>(mainGraph);
		List<Vertex> neighbourhood = n.neighborListOf(v);
		neighbourhood.retainAll(set);
		return neighbourhood;
	}

	// Marks vertices from maximal clique
	public void markClique() {
		for (Vertex v : mainGraph.vertexSet()) {
			if (maxClique.containsVertex(v)) {
				v.toClique();
			}
		}
	}

	public UndirectedGraph<Vertex, DefaultEdge> getGraph() {
		return mainGraph;
	}
}